S01-07 基础-算法基础
[TOC]
排序
排序介绍
排序是将多个数据按指定顺序排列的过程。
排序分类
- 内部排序：所有数据加载到内部存储器（内存）中排序，包括：
- 交换式排序法（如冒泡排序）
- 选择式排序法
- 插入式排序法
- 外部排序法：数据量过大，无法全部加载到内存，需借助外部存储（如硬盘）排序，包括：
- 合并排序法
- 直接合并排序法
冒泡排序
冒泡排序（Bubble Sorting）：通过对待排序序列从后向前（下标较大的元素开始），依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前移向后部（类似气泡上浮）。
案例：冒泡排序实现
将无序数组{24,69,80,57,13}排成从小到大的有序数列。
思路分析：
- n 个元素需进行 n-1 轮排序（外层循环次数）。
- 每轮排序确定一个元素的最终位置（从最大到最小依次归位）。
- 每轮比较次数 = 数组长度 - 1 - 当前轮数（内层循环次数）。
- 核心逻辑：相邻元素逆序则交换。
实现步骤：
数组初始状态：[24,69,80,57,13]
- 第 1 轮排序（目标：最大数 80 移到末尾）：
- 比较 24&69（不交换）→ 69&80（不交换）→ 80&57（交换 →[24,69,57,80,13]）→ 80&13（交换 →[24,69,57,13,80]）
- 第 2 轮排序（目标：第二大数 69 移到倒数第二）：
- 比较 24&69（不交换）→ 69&57（交换 →[24,57,69,13,80]）→ 69&13（交换 →[24,57,13,69,80]）
- 第 3 轮排序（目标：第三大数 57 移到倒数第三）：
- 比较 24&57（不交换）→ 57&13（交换 →[24,13,57,69,80]）
- 第 4 轮排序（目标：第四大数 24 移到倒数第四）：
- 比较 24&13（交换 →[13,24,57,69,80]）
代码实现：
public class BubbleSort {
public static void main(String[] args) {
int[] arr = {24, 69, 80, 57, 13, -1, 30, 200, -110};
int temp = 0; // 辅助交换的变量
// 外层循环：控制排序轮数（n个元素需n-1轮）
for (int i = 0; i < arr.length - 1; i++) {
// 内层循环：每轮比较次数（每轮减少1次，因为末尾已排好序）
for (int j = 0; j < arr.length - 1 - i; j++) {
// 相邻元素比较，逆序则交换（从小到大排序）
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
// 输出每轮排序结果
System.out.println("\n==第" + (i+1) + "轮==");
for (int j = 0; j < arr.length; j++) {
System.out.print(arr[j] + "\t");
}
}
}
}查找
在 Java 中，常用的查找方式有两种：
- 顺序查找（本章重点）
- 二分查找（后续算法讲解）
顺序查找
需求：有一个数列：{"白眉鹰王", "金毛狮王", "紫衫龙王", "青翼蝠王"}，从键盘输入一个名称，判断数列中是否包含该名称。若找到，提示找到并给出下标；若未找到，提示未找到。
思路分析：
- 定义字符串数组存储目标数列。
- 接收用户输入的查找名称。
- 遍历数组，逐一比较（字符串比较用
equals方法）。 - 用变量
index标记找到的下标（初始值-1，未找到则保持-1）。
代码实现：
import java.util.Scanner;
public class SeqSearch {
public static void main(String[] args) {
// 目标数组
String[] names = {"白眉鹰王", "金毛狮王", "紫衫龙王", "青翼蝠王"};
Scanner myScanner = new Scanner(System.in);
System.out.println("请输入名字：");
String findName = myScanner.next();
// 查找逻辑
int index = -1; // 标记下标（未找到为-1）
for (int i = 0; i < names.length; i++) {
// 比较输入名称与数组元素
if (findName.equals(names[i])) {
System.out.println("恭喜你找到" + findName);
System.out.println("下标为= " + i);
index = i; // 更新下标
break; // 找到后退出循环
}
}
二分查找（有序数组）
二分查找（Binary Search，折半查找）：是一种非常高效的搜索算法。它的核心思想是通过不断将搜索区间分成两半，来快速缩小查找范围，最终找到目标值。
前提：二分查找只能用于「已经排好序」的数组或集合中。
以下是关于 Java 中二分查找算法的详细介绍。
算法工作原理
二分查找的逻辑非常直观，类似于我们在字典中找一个单词，或者在玩“猜数字”游戏（猜 1 到 100 之间的一个数，每次告诉你猜大了还是猜小了）。
具体步骤如下：
初始化指针：定义两个指针，
left指向数组起始位置（0），right指向数组末尾位置（length - 1）。计算中间位置：计算
left和right的中间索引mid。比较与移动指针：
- 如果
array[mid] == target，说明找到了目标，直接返回索引mid。 - 如果
array[mid] < target，说明目标值在右半区间，因此将左指针移动到中间位置的右边：left = mid + 1。 - 如果
array[mid] > target，说明目标值在左半区间，因此将右指针移动到中间位置的左边：right = mid - 1。
- 如果
循环结束条件：当
left > right时，说明搜索区间为空，数组中不存在目标值，返回-1。
Java 代码实现
在 Java 中，二分查找通常有两种实现方式：迭代法（While 循环，推荐） 和 递归法。在实际工程中，通常推荐使用迭代法，因为它不会产生额外的函数调用栈开销，且避免了深度递归可能引发的 StackOverflowError。
迭代法
public class BinarySearch {
/**
* 二分查找（迭代版）
* @param nums 已排序的数组（假设为升序）
* @param target 需要查找的目标值
* @return 目标值在数组中的索引，如果未找到则返回 -1
*/
public static int search(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return -1;
}
// 初始化指针：left 和 right
int left = 0;
int right = nums.length - 1;
// 注意这里是 left <= right，因为 left 和 right 指向同一个元素时，也需要检查该元素
while (left <= right) {
// 重点防坑：使用 left + (right - left) / 2 而不是 (left + right) / 2
int mid = left + (right - left) / 2;
递归法
递归法:
public class BinarySearchRecursive {
public static int search(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return -1;
}
return binarySearch(nums, target, 0, nums.length - 1);
}
private static int binarySearch(int[] nums, int target, int left, int right) {
// 递归终止条件
if (left > right) {
return -1;
}
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
// 递归右半区间
return binarySearch(nums, target, mid + 1, right);
} else {
// 递归左半区间
return binarySearch(nums, target, left, mid - 1);
}
}
}算法复杂度分析
算法复杂度分析:
- 时间复杂度：。每次比较后，搜索范围都会减半。这意味着即使在一个包含 40 亿个元素的数组中查找，最多也只需要比较 32 次，效率极高。
- 空间复杂度：
- 迭代法：，只需要常数级别的额外空间来存储
left、right和mid指针。 - 递归法：，因为每次递归调用都需要在调用栈上分配空间，最大深度取决于树的高度（即二分的次数）。
核心易错点：Mid 的计算
核心易错点：Mid 的计算:
初学者经常将中间索引计算为：
int mid = (left + right) / 2;
虽然数学上完全正确，但在 Java 编程中这是一个隐藏的 Bug。如果 left 和 right 都非常大（接近 Integer.MAX_VALUE），它们的和可能会超出 32 位整型的最大值，导致整型溢出，从而变成负数，最终抛出 ArrayIndexOutOfBoundsException。
正确的写法是：
int mid = left + (right - left) / 2;
或者使用无符号右移（更高效）：
int mid = (left + right) >>> 1; （这也是 Java 官方 Arrays.binarySearch() 源码中采用的写法）。
Java 内置的二分查找 API
Java 内置的二分查找 API:
在实际开发中，你通常不需要手写二分查找，Java 的 java.util.Arrays 和 java.util.Collections 工具类已经提供了内置方法：
- 对于数组：
Arrays.binarySearch(array, target) - 对于列表 (List)：
Collections.binarySearch(list, target)
注意：如果内置 API 找到了元素，它会返回其索引。如果没有找到，它会返回
-(插入点) - 1。这个特性非常有用，它可以告诉你如果要把这个数字插入数组并保持有序，应该插在哪个位置。